package cn.edu.xjtu.work.binaryTreePaths;

import java.util.ArrayList;
import java.util.List;

import cn.edu.xjtu.Util.TreeNode.TreeNode;

/**
 * 257. 二叉树的所有路径
 * 
 * 给定一个二叉树，返回所有从根节点到叶子节点的路径。
 */
public class Solution {
  public List<String> binaryTreePaths(TreeNode root) {
    List<String> all = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    search(root, path, all);
    return all;
  }

  public void search(TreeNode root, List<Integer> path, List<String> all) {
    if (root == null) {
      return;
    }
    path.add(root.val);
    search(root.left, path, all);
    search(root.right, path, all);
    if (root.left == null && root.right == null) {
      all.add(toString(path));
    }
    path.remove(path.size() - 1);
  }

  public String toString(List<Integer> path) {

    StringBuilder sb = new StringBuilder();
    sb.append(path.get(0));
    for (int i = 1; i < path.size(); i++) {
      sb.append("->" + path.get(i));
    }
    return sb.toString();
  }
}
